/* Copyright (C) 2007-2010 STS Soft

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using STSdb.Data;
using System.Diagnostics;

namespace STSdb.Plan
{
    //public class XList<TRecord>
    //{
    //    private const ushort BLOCK_CAPACITY = 1024;

    //    private ulong autoKey = 0;
    //    private ushort depth;

    //    private XTable<XKey<ushort, ushort>, ulong[]> tree;
    //    private XTable<ulong, TRecord> data;

    //    public XList()
    //    {
    //    }

    //    public TRecord this[ulong index]
    //    {
    //        get
    //        {
    //            if (index >= Count)
    //                throw new ArgumentOutOfRangeException("index");

    //            Debug.Assert(depth >= 1);

    //            ushort idx = 0;
    //            ushort level = 0;
    //            for (; level < depth; level++)
    //            {
    //                ulong[] counts = tree[new XKey<ushort, ushort>(level, idx)];

    //                idx = 0;
    //                ulong sum = 0;
    //                while (/*idx < counts.Length && */ sum + counts[idx] <= index)
    //                {
    //                    sum = counts[idx];
    //                    idx++;
    //                }

    //                index -= sum;
    //            }

    //            ulong[] keys = tree[new XKey<ushort, ushort>(depth, idx)];

    //            return data[keys[index]];
    //        }

    //        set
    //        {
    //        }
    //    }

    //    public void Insert(TRecord record, ulong index)
    //    {
    //        if (index > Count)
    //            throw new ArgumentOutOfRangeException("index");

    //        if (index == Count)
    //        {
    //            //TODO: special case

    //            return;
    //        }


    //        List<XKey<ushort, ushort>> path = new List<XKey<ushort, ushort>>(depth + 1);

    //        ushort idx = 0;
    //        for (ushort level = 0; level < depth; level++)
    //        {
    //            var xkey = new XKey<ushort, ushort>(level, idx);
    //            path.Add(xkey);
    //            ulong[] counts = tree[xkey];

    //            idx = 0;
    //            ulong sum = 0;
    //            while (/*idx < counts.Length && */ sum + counts[idx] <= index)
    //            {
    //                sum += counts[idx];
    //                idx++;
    //            }

    //            index -= sum;
    //        }

    //        XKey<ushort, ushort> leaf = new XKey<ushort,ushort>(depth, idx);

    //        ulong[] keys = tree[leaf];

    //        if (keys.Length == 0)
    //        {
    //            //TODO:

    //            return; 
    //        }

    //        ulong[] newkeys = new ulong[keys.Length + 1];
    //        for (int i = 0; i < idx; i++)
    //            newkeys[i] = keys[i];
    //        for (int i = (int)index; i < keys.Length; i++)
    //            newkeys[i + 1] = keys[i];
    //        newkeys[index] = autoKey++;

    //        if (newkeys.Length <= BLOCK_CAPACITY)
    //        {
    //            tree[leaf] = newkeys;
    //            data[newkeys[index]] = record;
    //            return;
    //        }

    //        //TODO: split

    //        int j = path.Count - 1;

    //        do
    //        {



    //        }
    //        while (true);



    //    }

    //    public ulong Count
    //    {
    //        get { return data.Count; }
    //    }
    //}
}
